#include <iostream>
#include <cassert>
#include "DiGraph.h"
#include "Bag.h"
#include "AdjDiGraph.h"

using namespace std;

AdjDiGraph* getGraph(){
    int v = 13;
    const int e = 22;
    int vs[e*2] = {
            4,2, 2,3, 3,2, 6,0, 0,1, 2,0, 11,12, 12,9, 9,10, 9,11, 8,9, 10,12, 11,4,  4,3, 3,5, 7,8, 8,7, 5,4, 0,5, 6,4,
            6,9, 7,6
    };

    AdjDiGraph* graph = new AdjDiGraph(v);
    for (int i = 0; i < 2*e; i+=2) {
        graph->addEdge(vs[i],vs[i+1]);
    }
    return graph;
}

AdjDiGraph* getDAGGraph(){
    int v = 13;
    const int e = 15;
    int vs[e*2] = {
            0,5, 0,1, 0,6, 2,0, 2,3, 3,5, 5,4, 6,4, 6,9, 7,6, 8,7, 9,10, 9,11, 9,12, 11,12
    };

    AdjDiGraph* graph = new AdjDiGraph(v);
    for (int i = 0; i < 2*e; i+=2) {
        graph->addEdge(vs[i],vs[i+1]);
    }
    return graph;
}

int testAdjDiGraph() {
    AdjDiGraph* graph = getGraph();
    graph->print();

    delete graph;
    return 0;
}

int testDirectedGraph(int source, vector<int>* vsouces) {
    AdjDiGraph* graph = getGraph();
    AdjDiGraph* graph2 = getGraph();
    DirectedDFS* sch = new DirectedDFSImpl(graph,source);
    DirectedDFS* sch2 = new DirectedDFSImpl(graph2,vsouces);
    cout << source << " connect vertexs is: ";
    for (int j = 0; j < graph->V(); ++j) {
        if (sch->marked(j)) {
            cout << j << " ";
        }
    }
    cout<<endl;
    int vsourcesSize = vsouces->size();
    for (int i = 0; i < vsourcesSize; ++i) {
        cout << (*vsouces)[i] << " ";
    }
    cout<< " connect vertexs is: ";
    for (int j = 0; j < graph2->V(); ++j) {
        if (sch2->marked(j)) {
            cout << j << " ";
        }
    }
    cout << endl;

    delete sch;
    delete sch2;
    delete graph2;
    delete graph;
}

int testDirectedPaths(DirectedPaths*  dfp,AdjDiGraph* graph, int source) {
    for (int j = 0; j < graph->V(); ++j) {
        if (dfp->hasPathTo(j)) {
            cout<<source << " to "<<j<<": ";
            stack<int>* stack1 = dfp->pathTo(j);
            while(!stack1->empty()){
                cout<<stack1->top() << "->";
                stack1->pop();
            }
            delete stack1;
            cout << endl;
        }
    }

    delete dfp;
    delete graph;
}

int testDirectedPaths() {
    int source = 7;
    AdjDiGraph* graph = getGraph();
    AdjDiGraph* graph2 = getGraph();
    DepthFirstDirectedPaths*  dfp = new DepthFirstDirectedPaths(graph,source);
    BreadthFirstDirectedPaths*  bfs = new BreadthFirstDirectedPaths(graph2,source);

    cout<<"test DepthFirstPaths:";
    testDirectedPaths(dfp,graph,source);

    cout<<"test BreadthFirstPaths:";
    testDirectedPaths(bfs,graph2,source);

    delete graph;
    delete dfp;
    delete graph2;
    delete bfs;
    return 0;
}

int testDirectedCycle() {
    AdjDiGraph* graph = getGraph();
    DirectedCycle* cycle = new DfsDirectedCycle(graph);

    cout<<"testDirectedCycle:";
    cout<< (cycle->hasCycle()?"have cycle":"don't have cycle") <<endl;

    if(cycle->hasCycle()) {
        cout<<"cycle path :";
        stack<int>* stack1 = cycle->cycle();
        while(!stack1->empty()){
            cout<<stack1->top()<<"->";
            stack1->pop();
        }
        cout<<endl;
    }

    delete graph;
    delete cycle;
    return 0;
}

int testDirectedOrder(){

//    AdjDiGraph* graph = getDAGGraph();
//    DirectedOrder* directedOrder = new DirectedOrderImpl(graph);
//
//    cout<<"testDirectedOrder:";
//    cout<< (directedOrder->is()?"DAG":"not DAG") <<endl;
//
//    if(directedOrder->isDAG()) {
//        cout<<"DAG path :";
//        queue<int>* queue1 = topical->order();
//        while(!queue1->empty()){
//            cout<<queue1->front()<<"->";
//            queue1->pop();
//        }
//        cout<<endl;
//    }
//
//    delete graph;
//    delete topical;
    return 0;
}

int testTopological() {
    AdjDiGraph* graph = getDAGGraph();
    Topological* topical = new TopologicalImpl(graph);

    cout<<"testTopological:";
    cout<< (topical->isDAG()?"DAG":"not DAG") <<endl;

    if(topical->isDAG()) {
        cout<<"DAG path :";
        queue<int>* queue1 = topical->order();
        while(!queue1->empty()){
            cout<<queue1->front()<<"->";
            queue1->pop();
        }
        cout<<endl;
    }

    delete graph;
    delete topical;
    return 0;
}


int testKosarajuSCC() {
    AdjDiGraph* graph = getGraph();
    KosarajuSCC* scc = new DepthFirstKosarajuSCC(graph);

    int M = scc->count();
    cout<< M << " components"<<endl;

    Bag<int>* components = new Bag<int>[M];
    for (int i = 0; i < M; ++i) {
        components[i] = *(new Bag<int>());
    }

    for (int j = 0; j < graph->V(); ++j) {
        components[scc->id(j)].add(j);
    }

    for (int k = 0; k < M; ++k) {
        vector<int>* vector1 = components[k].getVector();
        int size = vector1->size();
        for (int j =0; j < size; ++j) {
            cout << (*vector1)[j] << " ";
        }
        cout<<endl;
        delete vector1;
    }


    delete[] components;
    delete scc;
    delete graph;
}

int main() {
//    testAdjDiGraph();//打印测试，正确性测试
//    vector<int>* vector1 = new vector<int>({1,2,7});
//    testDirectedGraph(6,vector1);//可达性测试
//    testDirectedPaths();//路径，最短路径测试
//    testDirectedCycle();//测试是否有环
//    testDirectedOrder();//测试排序
//    testTopological();//测试拓扑有序
    testKosarajuSCC();//测试强连通分量
    return 0;
}